/*************************************************************
*
* CGM_WED.CPP
*
* Winged-edge polygon mesh representation
* Basic functionality
*************************************************************/
#include <m3d/m3d_stdafx.h>

#include <ap_comm.h>
#include <m3d.h>
#include <objects.h>

#include <cgm.h>

#define _CGM_WED_ALLOC_FACTOR       100
#define _CGM_WED_ALLOC_GRANULARITY  100

//
// Static variables
//
static cgmQUERY  _cgmWedQueryDefault;


/*************************************************************
* cgmWED_SYS::cgmWED_SYS()
*
*************************************************************/
cgmWED_SYS::cgmWED_SYS() 
   : processedState(HIGHEST_PROCESSED_STATE)
{ 
   nNode    = 0;
   nodeList = NULL;
   nEdge    = 0;
   edgeList = NULL;
   nFace    = 0;
   faceList = NULL;
   nodeQueue= NULL;
   faceQueue= NULL;
   nNodeAllocated = 0;
   nEdgeAllocated = 0;
   nFaceAllocated = 0;

   // create the default query, if needed
   if (pQueryDefault == NULL) {
      pQueryDefault = &_cgmWedQueryDefault;
   }

   faceEdgeList = NULL; 
   nodeEdgeList = NULL; 

   return;
}

/*************************************************************
* cgmWED_SYS::Init ()
*    Create a winged-edge data structure from a compatible
* representation of a polygon mesh
* 
* IN  : none (all mesh info is passed via virtualized interfaces MeshGetXXX()
* OUT : winged-edge structure
* RET : FALSE if an error occured
*************************************************************/
BOOL cgmWED_SYS::Init (void)
{
   cgmWED_FACE  *pFace;
   int           i, j, nEdgeTotal;
   int           nFaceVert, nNodeEdgeTotal, nFaceEdgeTotal;

   // calc total number of possible edges
   nEdgeTotal = 0;
   for (i = 0; i < MeshGetNFace(); i ++) {
      nEdgeTotal += MeshGetFaceNVert(i);
   }

   // alloc all lists
   if (!Realloc(MeshGetNVert(), nEdgeTotal, MeshGetNFace())) {
      goto exit_with_error;
   }

   // nNode/nFace must be set AFTER Realloc() - it is assumed that they are zero
   // bofore the first call
   nNode = MeshGetNVert();
   nFace = MeshGetNFace();

   memset(nodeList, 0, nNode     * sizeof(cgmWED_NODE));
   memset(edgeList, 0, nEdgeTotal * sizeof(cgmWED_EDGE));
   memset(faceList, 0, nFace     * sizeof(cgmWED_FACE));

   // count upper limits of edges incident to nodes/faces
   nNodeEdgeTotal = 0;
   nFaceEdgeTotal = 0;
   for (i = 0; i < nFace; i ++) {
      for(j = 0; j < MeshGetFaceNVert(i); j ++) {
         nodeList[MeshGetFaceVertInd(i, j)].nEdge += 2;
         nNodeEdgeTotal += 2;
      }
      nFaceEdgeTotal += MeshGetFaceNVert(i);
   }

   // Alloc linear array of node edges
   if ((nodeEdgeList = (cgmWED_EDGE**)calloc(nNodeEdgeTotal, sizeof(cgmWED_EDGE*))) == NULL) {
      return FALSE;
   }
   // init edge list for each node
   nNodeEdgeTotal = 0;
   for (i = 0; i < nNode; i ++) {
      nodeList[i].ind      = i;
      nodeList[i].edgeList = &nodeEdgeList[nNodeEdgeTotal];
      nNodeEdgeTotal += nodeList[i].nEdge;
#ifdef _DEBUG
      nodeList[i].maxNEdge = nodeList[i].nEdge;
#endif
      nodeList[i].nEdge = 0;
   }

   // Alloc linear array of face edges
   if ((faceEdgeList = (cgmWED_EDGE**)calloc(nFaceEdgeTotal, sizeof(cgmWED_EDGE*))) == NULL) {
      return FALSE;
   }
   // init list of faces
   nFaceEdgeTotal = 0;
   for (i = 0; i < nFace; i ++) {
      pFace           = &faceList[i];
      pFace->ind      = i;
      pFace->edgeList = &faceEdgeList[nFaceEdgeTotal];

      nFaceVert = MeshGetFaceNVert(i);
      // add all face edges to data structure
      if (!AddFaceEdge(pFace, MeshGetFaceVertInd(i, nFaceVert-1), MeshGetFaceVertInd(i, 0))) {
         goto exit_with_error;
      }
      for(j = 1; j < nFaceVert; j ++) {
         if (!AddFaceEdge(pFace, MeshGetFaceVertInd(i, j-1), MeshGetFaceVertInd(i, j))) {
            goto exit_with_error;
         }
      }
      nFaceEdgeTotal += nFaceVert;
   }

   // adjust lists to proper size
   if (!Realloc(nNode, nEdge, nFace)) {
      goto exit_with_error;
   }
   if (!UpdateInternal()) {
      goto exit_with_error;
   }

   Check();

   return TRUE;
exit_with_error:
   Term();
   return FALSE;
}

/*************************************************************
* cgmWED_SYS::Term ()
*    Free a winged-edge data structure 
*
* IN  : winged-edge structure 
*************************************************************/
void cgmWED_SYS::Term (void)
{
   int i;

   for (i = 0; i < nEdge; i ++) {
      free(edgeList[i].addFaceList);
   }
   free(edgeList);
   edgeList = NULL;
   nEdge    = 0;

   free(nodeList);
   nodeList = NULL;
   nNode    = 0;
   
   free(nodeQueue);
   free(faceQueue);
   nodeQueue   = NULL;
   faceQueue   = NULL;

   free(faceList);
   faceList = NULL;
   nFace    = 0;

   free(faceEdgeList);
   free(nodeEdgeList);
   faceEdgeList = NULL; 
   nodeEdgeList = NULL; 
   
   nNodeAllocated = 0;
   nEdgeAllocated = 0;
   nFaceAllocated = 0;

   return;
}

/*************************************************************
* cgmWED_SYS::Merge ()
*    Merge two winged-edge structures
* 
* IN  : pWedAdd - winged-edge to Merge 
* OUT : pWedUnion - union of two weds
* RET : FALSE if an error occured
*************************************************************/
BOOL cgmWED_SYS::Merge (cgmWED_SYS *pWedAdd)
{
/*
   cgmWED_NODE  *pNode;
   cgmWED_FACE  *pFace;
   cgmWED_EDGE  *pEdge;
   int           i, j;
   // alloc all lists
   if (!Realloc(pWedAdd->nNode + nNode, pWedAdd->nEdge + nEdge, pWedAdd->nFace + nFace)) {
      goto exit_with_error;
   }

   // copy information about nodes
   for (i = 0; i < pWedAdd->nNode; i ++) {
      pNode = &nodeList[nNode + i];
      _ZeroStruct(pNode);

      pNode->ind   = nNode + i;
      pNode->nEdge = pWedAdd->nodeList[i].nEdge;
      if ((pNode->edgeList = (cgmWED_EDGE**)malloc(pNode->nEdge*sizeof(cgmWED_EDGE*))) == NULL) {
         goto exit_with_error;
      }
      pNode->nEdgeAllocated = pNode->nEdge;
      pNode->nEdgeExtra = 0;
      for (j = 0; j < pNode->nEdge; j ++) {
         // update pointer to edge
         pNode->edgeList[j] = &edgeList[nEdge + pWedAdd->nodeList[i].edgeList[j]->ind];
      }
   }

   // copy information about faces
   for (i = 0; i < pWedAdd->nFace; i ++) {
      pFace = &faceList[nFace + i];
      _ZeroStruct(pFace);

      pFace->ind   = nFace + i;
      pFace->nEdge = pWedAdd->faceList[i].nEdge;
      if ((pFace->edgeList = (cgmWED_EDGE**)malloc(pFace->nEdge*sizeof(cgmWED_EDGE*))) == NULL) {
         goto exit_with_error;
      }
      for (j = 0; j < pFace->nEdge; j ++) {
         // update pointer to edge
         pFace->edgeList[j] = &edgeList[nEdge + pWedAdd->faceList[i].edgeList[j]->ind];
      }
   }

   // copy information about edges
   for (i = 0; i < pWedAdd->nEdge; i ++) {
      pEdge = &edgeList[nEdge + i];
      _ZeroStruct(pEdge);

      pEdge->ind = nEdge + i;
      // update pointers to nodes
      pEdge->pNode1 = &nodeList[nNode + pWedAdd->edgeList[i].pNode1->ind];
      pEdge->pNode2 = &nodeList[nNode + pWedAdd->edgeList[i].pNode2->ind];
      // update pointers to faces
      pEdge->pFace1 = &faceList[nFace + pWedAdd->edgeList[i].pFace1->ind];
      if (pEdge->pFace2 != NULL) {
         pEdge->pFace2 = &faceList[nFace + pWedAdd->edgeList[i].pFace2->ind];
      }
   }
   nNode += pWedAdd->nNode;
   nFace += pWedAdd->nFace;
   nEdge += pWedAdd->nEdge;
   return TRUE;
exit_with_error:
*/   
   return FALSE;
}

/*************************************************************
* cgmWED_SYS::AddDummyEdge ()
*    Add dummy edge to wed structure
*
* IN: node IDs
*************************************************************/
BOOL cgmWED_SYS::AddDummyEdge (int nodeInd1, int nodeInd2)
{
   cgmWED_EDGE  *pEdge;
   cgmWED_NODE  *pNode1, *pNode2;

   // add edge to edge list
   if (!Realloc(nNode, nEdge + 1, nFace)) {
      goto exit_with_error;
   }
   pEdge  = &edgeList[nEdge];
   _ZeroStruct(pEdge);
   pNode1 = &nodeList[nodeInd1];
   pNode2 = &nodeList[nodeInd2];
   pEdge->ind    = nEdge;
   pEdge->pNode1 = pNode1;
   pEdge->pNode2 = pNode2;
   // add edge to node edge lists
   if (!AddNodeEdge(pNode1, pEdge) || !AddNodeEdge(pNode2, pEdge)) {
      goto exit_with_error;
   }
   nEdge ++;
   return TRUE;
exit_with_error:
   return FALSE;
}

/*************************************************************
* cgmWED_SYS::UpdateInternal()
*
* Allocate arrays, needed for some algorithms
* RET : FALSE if an error occured
*************************************************************/
BOOL cgmWED_SYS::UpdateInternal (void)
{
   // alloc node queue for search algorithms
   if ((nodeQueue = (cgmWED_NODE**)realloc(nodeQueue, nNode*sizeof(cgmWED_NODE*))) == NULL) {
      return FALSE;
   }
   if ((faceQueue = (cgmWED_FACE**)realloc(faceQueue, nFace*sizeof(cgmWED_FACE*))) == NULL) {
      return FALSE;
   }
   return TRUE;
}

/*************************************************************
* cgmWED_NODE::IncidentNode()
*
*************************************************************/
cgmWED_NODE* cgmWED_NODE::IncidentNode (cgmWED_EDGE *pEdge) 
{
   if (pEdge->pNode1 == this) {
      return pEdge->pNode2;
   }
   ASSERT(pEdge->pNode2 == this);
   return pEdge->pNode1;
}

/*************************************************************
* cgmWED_NODE::GetNodeEdgeInd()
*   Find an adge in node edge list
*
* IN  : node, index of incident node
* RET : edge index in list of node edges, if found, or -1
*************************************************************/
int cgmWED_NODE::GetNodeEdgeInd (int nodeInd)
{
   int            i;
   cgmWED_NODE   *pIncNode;

   for (i = 0; i < nEdge; i ++) {
      pIncNode = IncidentNode(edgeList[i]);

      if (pIncNode->ind == nodeInd) {
         return i;
      }
   }
   return -1;
}

/*************************************************************
* cgmWED_NODE::IsIncidentNode()
*   Check if pNode is incident to the given node along a 
* certain edge
* 
* IN  : first edge node, second edge node
* RET : edge found, or NULL
*************************************************************/
cgmWED_EDGE* cgmWED_NODE::IsIncidentNode (cgmWED_NODE *pNode)
{
   cgmWED_EDGE *pEdge;
   int          i;

   for (i = 0; i < nEdge; i ++) {
      pEdge = edgeList[i];
      if (IncidentNode(pEdge) == pNode) {
         return pEdge;
      }
   }
   return NULL;
}

/*************************************************************
* cgmWED_NODE::IsIncidentEdge()
*
*************************************************************/
int cgmWED_NODE::GetEdgeInd (cgmWED_EDGE *pEdge) 
{
   int          i;

   for (i = 0; i < nEdge; i ++) {
      if (pEdge == edgeList[i]) {
         return i;
      }
   }
   return -1;
}
/*************************************************************
* cgmWED_NODE::IsIncidentEdge()
*
*************************************************************/
int cgmWED_NODE::GetIncidentFaceList (cgmWED_FACE ** ppFaceList, int maxNFace)
{
   cgmWED_FACE *pFace;
   int          i, j, k, nFace;

   nFace = 0;
   for (i = 0; i < nEdge; i ++) {
      for (j = 0; j < 2 + edgeList[i]->nAddFace; j ++) {
         if (j == 0) {
            pFace = edgeList[i]->pFace1;
         } else if (j == 1) {
            pFace = edgeList[i]->pFace2;
         } else {
            pFace = edgeList[i]->addFaceList[j-2];
         }
         for (k = 0; k < nFace; k ++) {
            if (ppFaceList[k] == pFace) {
               break;
            }
         }
         if (pFace != NULL && k >= nFace && nFace < maxNFace) {
            ppFaceList[nFace ++] = pFace;
         }
      }
   }
   ASSERT(nFace < maxNFace);
   return nFace;
}

/*************************************************************
* cgmWED_FACE::IncidentFace()
*
*************************************************************/
cgmWED_FACE* cgmWED_FACE::IncidentFace (cgmWED_EDGE *pEdge) 
{
   if (pEdge->pFace2 == this) {
      return pEdge->pFace1;
   }
   for(int i = 0; i < pEdge->nAddFace; i ++) {
      if (pEdge->addFaceList[i] == this) {
         return pEdge->addFaceList[i];
      }
   }
   ASSERT(pEdge->pFace1 == this);
   return pEdge->pFace2;
}

/*************************************************************
* cgmWED_FACE::cgmWED_FACE::FindEdge ()
*
*************************************************************/
cgmWED_EDGE* cgmWED_FACE::FindEdge (int nodeInd1, int nodeInd2)
{
   int  i;

   for (i = 0; i < nEdge; i ++) {
      if ((edgeList[i]->pNode1->ind == nodeInd1 && edgeList[i]->pNode2->ind == nodeInd2) ||
          (edgeList[i]->pNode1->ind == nodeInd2 && edgeList[i]->pNode2->ind == nodeInd1)) {
         return edgeList[i];
      }
   }
   ASSERT(FALSE);
   return NULL;
}

/*************************************************************
* cgmWED_SYS::UpdatePointer ()
*    Update pointer to array element after array realloc
* IN  : oldArrStartAdr - old address of arrays head 
*       newArrStartAdr - new address of arrays head 
*       arrElemPtr - address of array element
* OUT : none
* RET : new addres of element
*************************************************************/
void* cgmWED_SYS::UpdatePointer (void *oldArrStartAdr, void *newArrStartAdr, void *arrElemPtr)
{
   int offset;
   ASSERT(oldArrStartAdr != NULL && newArrStartAdr != NULL && arrElemPtr != NULL);

   offset = ((BYTE*)arrElemPtr) - ((BYTE*)oldArrStartAdr);
   return ((BYTE*)newArrStartAdr ) + offset;
}

/*************************************************************
* cgmWED_SYS::Realloc ()
*    Realloc wed lists and update all pointers
* IN  : pWedAdd - winged-edge to Merge 
* OUT : pWedUnion - union of two weds
* RET : FALSE if an error occured
*************************************************************/
BOOL cgmWED_SYS::Realloc (int nNodeNew, int nEdgeNew, int nFaceNew)
{
   cgmWED_NODE  *pNode, *nodeListNew;
   cgmWED_FACE  *pFace, *faceListNew;
   cgmWED_EDGE  *pEdge, *edgeListNew;
   int           nNodeAllocated, nFaceAllocated, nEdgeAllocated;
   int           i, j;
   int           gran;  // allocation granularity

   gran = max(nNodeNew / _CGM_WED_ALLOC_FACTOR, _CGM_WED_ALLOC_GRANULARITY);
   nNodeAllocated = this->nNodeAllocated;
   if (nNodeNew + gran < this->nNodeAllocated) {
      nNodeAllocated = nNodeNew + gran / 2;
   } else if (nNodeNew > this->nNodeAllocated) {
      nNodeAllocated = nNodeNew + gran;
   } 

   gran = max(nEdgeNew / _CGM_WED_ALLOC_FACTOR, _CGM_WED_ALLOC_GRANULARITY);
   nEdgeAllocated = this->nEdgeAllocated;
   if (nEdgeNew + gran < this->nEdgeAllocated) {
      nEdgeAllocated = nEdgeNew + gran / 2;
   } else if (nEdgeNew > this->nEdgeAllocated) {
      nEdgeAllocated = nEdgeNew + gran;
   } 

   gran = max(nFaceNew / _CGM_WED_ALLOC_FACTOR, _CGM_WED_ALLOC_GRANULARITY);
   nFaceAllocated = this->nFaceAllocated;
   if (nFaceNew + gran < this->nFaceAllocated) {
      nFaceAllocated = nFaceNew + gran / 2;
   } else if (nFaceNew > this->nFaceAllocated) {
      nFaceAllocated = nFaceNew + gran;
   }

   if (nNodeAllocated != this->nNodeAllocated) {
      if ((nodeListNew = (cgmWED_NODE*)realloc(this->nodeList, nNodeAllocated*sizeof(cgmWED_NODE))) == NULL) {
         goto exit_with_error;
      }
      this->nNodeAllocated = nNodeAllocated;
   } else {
      nodeListNew = this->nodeList;
   }

   if (nFaceAllocated != this->nFaceAllocated) {
      if ((faceListNew = (cgmWED_FACE*)realloc(this->faceList, nFaceAllocated*sizeof(cgmWED_FACE))) == NULL) {
         goto exit_with_error;
      }
      this->nFaceAllocated = nFaceAllocated;
   } else {
      faceListNew = this->faceList;
   }

   if (nEdgeAllocated != this->nEdgeAllocated) {
      if ((edgeListNew = (cgmWED_EDGE*)realloc(this->edgeList, nEdgeAllocated*sizeof(cgmWED_EDGE))) == NULL) {
         goto exit_with_error;
      }
      this->nEdgeAllocated = nEdgeAllocated;
   } else {
      edgeListNew = this->edgeList;
   }

   if (edgeListNew != this->edgeList) {
      // Update pointers to edges after realloc
      for (i = 0; i < this->nNode; i ++) {
         pNode = &nodeListNew[i];
         for (j = 0; j < pNode->nEdge; j ++) {
            // update pointer to edge
            pNode->edgeList[j] = (cgmWED_EDGE*)UpdatePointer(this->edgeList, edgeListNew, pNode->edgeList[j]);
         }
      }
      // Update pointers to edges after realloc
      for (i = 0; i < this->nFace; i ++) {
         pFace = &faceListNew[i];
         for (j = 0; j < pFace->nEdge; j ++) {
            // update pointer to edge
            pFace->edgeList[j] = (cgmWED_EDGE*)UpdatePointer(this->edgeList, edgeListNew, pFace->edgeList[j]);
         }
      }
      this->edgeList = edgeListNew;
   }

   if (nodeListNew != this->nodeList) {
      // Update pointers to nodes or faces after realloc
      for (i = 0; i < this->nEdge; i ++) {
         pEdge = &edgeListNew[i];
         // update pointers to nodes
         pEdge->pNode1 = (cgmWED_NODE*)UpdatePointer(this->nodeList, nodeListNew, pEdge->pNode1);
         pEdge->pNode2 = (cgmWED_NODE*)UpdatePointer(this->nodeList, nodeListNew, pEdge->pNode2);
      }
      this->nodeList = nodeListNew;
   }

   if (faceListNew != this->faceList) {
      // Update pointers to nodes or faces after realloc
      for (i = 0; i < this->nEdge; i ++) {
         pEdge = &edgeListNew[i];
         // update pointers to faces
         if (pEdge->pFace1 != NULL) {
            pEdge->pFace1 = (cgmWED_FACE*)UpdatePointer(this->faceList, faceListNew, pEdge->pFace1);
         }
         if (pEdge->pFace2 != NULL) {
            pEdge->pFace2 = (cgmWED_FACE*)UpdatePointer(this->faceList, faceListNew, pEdge->pFace2);
         }
      }
      this->faceList = faceListNew;
   }

   return TRUE;
exit_with_error:
   return FALSE;
}

/*************************************************************
* cgmWED_SYS::AddFaceEdge ()
*    Add edge to edge list
* 
* RET : FALSE if an error occured
*************************************************************/
BOOL cgmWED_SYS::AddFaceEdge (cgmWED_FACE *pFace, int nodeInd1, int nodeInd2)
{
   cgmWED_NODE *pNode1, *pNode2;
   cgmWED_EDGE *pEdge;
   int          edgeInd;
   
   pNode1 = &nodeList[nodeInd1];
   pNode2 = &nodeList[nodeInd2];
   edgeInd = pNode1->GetNodeEdgeInd(pNode2->ind);
   if (edgeInd == -1) {
      ASSERT(NULL == pNode1->IsIncidentNode(pNode2));
      // add edge to global edge list
      pEdge = &edgeList[nEdge];
      pEdge->ind = nEdge;
      nEdge ++;
      // store & init edge parameters
      pEdge->pNode1         = pNode1;
      pEdge->pNode2         = pNode2;
      pEdge->pFace1         = pFace;
      pEdge->pFace2         = NULL;
      pEdge->processedState = 0;
      // add edge to lists of nodes edges
      if (!AddNodeEdge(pNode1, pEdge) || !AddNodeEdge(pNode2, pEdge)) {
         return FALSE;
      }
   } else {
      pEdge = pNode1->edgeList[edgeInd];
      ASSERT(pEdge == pNode1->IsIncidentNode(pNode2));
      
      if (pEdge->pFace2 == NULL) {
         pEdge->pFace2  = pFace;
         if (pNode1 == pEdge->pNode1) {
            pEdge->state.Set(CGM_WED_ST_SAME_ORIENTED);
         }
      } else {
         pEdge->state.Set(CGM_WED_ST_BAD_EDGE);
         if ((pEdge->addFaceList = (cgmWED_FACE**)realloc(pEdge->addFaceList, (pEdge->nAddFace + 1) * sizeof(cgmWED_FACE*))) == NULL) {
            return FALSE;
         }
         pEdge->addFaceList[pEdge->nAddFace] = pFace;
         pEdge->nAddFace ++;
      }
   }
   // add edge to face edge list
   pFace->edgeList[pFace->nEdge] = pEdge;
   pFace->nEdge ++;
   
   return TRUE;
}

/*************************************************************
* cgmWED_SYS::AddNodeEdge ()
*   Add edge to node edge list 
* 
* IN  : winged-edge structure, node, edge
* OUT : none
* RET : number of edge in list or -1 if an error occured
*************************************************************/
BOOL cgmWED_SYS::AddNodeEdge(cgmWED_NODE *pNode, cgmWED_EDGE *pEdge)
{
//   cgmWED_EDGE **pEdgeList;  // new list of edges incident to given node
//   int           nEdges;     // number of edges to allocate

   ASSERT(pNode != NULL && pEdge != NULL);
#ifdef _DEBUG
   ASSERT(0 <= pNode->nEdge && pNode->nEdge <= pNode->maxNEdge);
#endif
/*
   // add edge to node edge list
   if (pNode->nEdge >= pNode->nEdgeAllocated) {
      nEdges = max(pNode->nEdge + 1, pNode->nEdgeAllocated + pNode->nEdgeExtra);
      if ((pEdgeList = (cgmWED_EDGE**)realloc(pNode->edgeList, nEdges * sizeof(*pEdgeList))) == NULL) {
         return FALSE;
      }
      pNode->edgeList = pEdgeList;
      // pNode->nEdgeExtra = max(pNode->nEdgeAllocated + pNode->nEdgeExtra - nEdges, 0);
      pNode->nEdgeAllocated = nEdges;
   }
*/
   pNode->edgeList[pNode->nEdge] = pEdge;
   pNode->nEdge ++;

//   ASSERT(pNode->nEdge <= pNode->nEdgeExtra);
   return TRUE;
}

/**************************************************************************
* cgmWED_SYS::ClearStates()                                               *
*                                                                         *
**************************************************************************/
void cgmWED_SYS::ClearStates(void)
{
   if (!_IsState(processedState, HIGHEST_PROCESSED_STATE)) {
      searchState = ++processedState;
   } else {
      _ClearState();
      processedState = searchState = 1;
   }
}

/*************************************************************
* cgmWED_SYS::ClearState ()
*   Clear all processed flags from nodes, edges and faces
* 
*************************************************************/
void cgmWED_SYS::_ClearState (void)
{
   // clear flags from all nodes
   for (int i = 0; i < nNode; i ++) {
      //nodeList[i].state.Clear(CGM_WED_ST_PROCESSED | CGM_WED_ST_START | CGM_WED_ST_SEARCH);
      nodeList[i].processedState = 0;
      nodeList[i].searchState    = 0;
   }
   // clear flags from all faces
   for (int i = 0; i < nFace; i ++) {
      //faceList[i].state.Clear(CGM_WED_ST_PROCESSED);
      faceList[i].processedState = 0;
      faceList[i].searchState    = 0;
   }
   // clear flags from all edges
   for (int i = 0; i < nEdge; i ++) {
      //edgeList[i].state.Clear(CGM_WED_ST_PROCESSED);
      edgeList[i].processedState = 0;
   }
}

/*************************************************************
* cgmWED_SYS::Check()
*
* Check WED consistency
*************************************************************/
BOOL cgmWED_SYS::Check (void)
{
   int            i;
   cgmWED_EDGE   *pE;

   for (i = 0; i < GetNEdge(); i++) {
      pE = GetEdge(i);
      if (pE->pNode1->GetEdgeInd(pE) == -1) {
         ASSERT(FALSE);
         return FALSE;
      }
      if (pE->pNode2->GetEdgeInd(pE) == -1) {
         ASSERT(FALSE);
         return FALSE;
      }
   }
   return TRUE;
}
/*************************************************************
* cgmWED_SYS::GetEdgeVertIndInFace ()
*
*************************************************************/
void cgmWED_SYS::GetEdgeVertIndInFace (cgmWED_FACE *pFace, cgmWED_EDGE *pEdge, int *ind1, int *ind2)
{
   int   i;

   *ind1 = *ind2 = -1;
   for (i = 0; i < MeshGetFaceNVert(pFace->ind); i ++) {
      if (MeshGetFaceVertInd(pFace->ind, i) == pEdge->pNode1->ind) {
         *ind1 = i;
      }
      if (MeshGetFaceVertInd(pFace->ind, i) == pEdge->pNode2->ind) {
         *ind2 = i;
      }
   }
   ASSERT(*ind1 != -1 && *ind2 != -1);
   return;
}

/*************************************************************
* wedSortEdges ()
*    Sort Node and face edge lists
* 
* IN  : winged-edge structure
* OUT : none
* RET : none
*************************************************************
void wedSortEdges (wedWED *pWed)
{
   wedFACE   *pFace;
   wedNODE   *pNode;
   int        i;

   // soft face edges
   for (i = 0; i < pWed->nFace; i ++) {
      pFace = &pWed->faceList[i];
      // transitive closure
      _wedSortEdgesTransitiveClosure(pWed, pFace->nEdge, pFace->edgeList, _wedCmpFaceEdgeCB, pFace);
   }
   // soft node edges
   for (i = 0; i < pWed->nNode; i ++) {
      pNode = &pWed->nodeList[i];
      // transitive closure
      _wedSortEdgesTransitiveClosure(pWed, pNode->nEdge, pNode->edgeList, _wedCmpNodeEdgeCB, pNode);
   }

   return;
}
*/
/*************************************************************
* _wedSortEdgesTransitiveClosure ()
*   
* 
* IN  : winged-edge structure, 
* OUT : none
* RET : 
*************************************************************
static void _wedSortEdgesTransitiveClosure (wedWED *pWed, int nEdge, wedEDGE **edgeList, _wedSORT_EDGE_CB cmpFaceEdgeCB, void *pUser)
{
   wedEDGE   **tmpEdgeList;
   int         i, j, k, edgeInd;

   tmpEdgeList = pWed->tmpEdgeList;
   memcpy(tmpEdgeList, edgeList, nEdge*sizeof(wedEDGE**));

   for (i = 0; i < nEdge; i ++) {
      // find any one edge
      for (k = 0; k < nEdge; k ++) {
         if (tmpEdgeList[k] != NULL) {
            edgeList[i] = tmpEdgeList[k];
            edgeInd     = k;
            break;
         }
      }
      // we have only a partially odered set of edges
      for (j = 0; j < nEdge; j ++) {
         for (k = 0; k < nEdge; k ++) {
            if (tmpEdgeList[k] == NULL) {
               continue;
            }
            if (cmpFaceEdgeCB(pWed, edgeList[i], tmpEdgeList[k], pUser) == _WED_LESS) {
               // store edge
               edgeList[i] = tmpEdgeList[k];
               edgeInd     = k;
            }
         }
      }
      // erase edge from list
      tmpEdgeList[edgeInd] = NULL;
   }
   return;
}
*/
/*************************************************************
* _wedCmpFaceEdgeCB()
*   
*   ???????????
* IN  : winged-edge structure, 
* OUT : none
* RET : 
*************************************************************
__INLINE BOOL wedGetFaceEdgeOrientation (wedFACE *pFace, wedEDGE *pEdge)
{
   if (pEdge->pFace1 == pFace) {
      return TRUE;
   }
   return FALSE;
}

static _wedCOMPARE _wedCmpFaceEdgeCB(wedWED *pWed, wedEDGE *pEdge1, wedEDGE *pEdge2, void *pUser)
{
   wedFACE *pFace = pUser;
   wedNODE *pEdge1Node[2], *pEdge2Node[2];

   if (wedGetFaceEdgeOrientation(pFace, pEdge1)) {
      pEdge1Node[0] = pEdge1->pNode1;
      pEdge1Node[1] = pEdge1->pNode2;
   } else {
      pEdge1Node[0] = pEdge1->pNode2;
      pEdge1Node[1] = pEdge1->pNode1;
   }
   if (wedGetFaceEdgeOrientation(pFace, pEdge2)) {
      pEdge2Node[0] = pEdge2->pNode1;
      pEdge2Node[1] = pEdge2->pNode2;
   } else {
      pEdge2Node[0] = pEdge2->pNode2;
      pEdge2Node[1] = pEdge2->pNode1;
   }
   if (pEdge1Node[0] == pEdge2Node[0] && pEdge1Node[1] == pEdge2Node[1]) {
      return _WED_EQUIVALENT;
   } else if (pEdge1Node[0] == pEdge2Node[1]) {
      return _WED_GREATER;
   } else if (pEdge1Node[1] == pEdge2Node[0]) {
      return _WED_LESS;
   }
   return _WED_INCOMPARABLE;
}
*/
/*************************************************************
* _wedCmpNodeEdgeCB ()
*   
*   ??????????
* IN  : winged-edge structure, 
* OUT : none
* RET : 
*************************************************************
__INLINE BOOL wedGetNodeEdgeOrientation (wedNODE *pNode, wedEDGE *pEdge)
{
   if (pEdge->pNode1 == pNode) {
      return TRUE;
   }
   return FALSE;
}
static _wedCOMPARE _wedCmpNodeEdgeCB(wedWED *pWed, wedEDGE *pEdge1, wedEDGE *pEdge2, void *pUser)
{
   wedNODE *pNode = pUser;
   wedFACE *pEdge1Face[2], *pEdge2Face[2];

   if (wedGetNodeEdgeOrientation(pNode, pEdge1)) {
      pEdge1Face[0] = pEdge1->pFace1;
      pEdge1Face[1] = pEdge1->pFace2;
   } else {
      pEdge1Face[0] = pEdge1->pFace2;
      pEdge1Face[1] = pEdge1->pFace1;
   }
   if (wedGetNodeEdgeOrientation(pNode, pEdge2)) {
      pEdge2Face[0] = pEdge2->pFace1;
      pEdge2Face[1] = pEdge2->pFace2;
   } else {
      pEdge2Face[0] = pEdge2->pFace2;
      pEdge2Face[1] = pEdge2->pFace1;
   }
   if (pEdge1Face[0] == pEdge2Face[0] && pEdge1Face[1] == pEdge2Face[1]) {
      return _WED_EQUIVALENT;
   } else if (pEdge1Face[0] == pEdge2Face[1]) {
      return _WED_GREATER;
   } else if (pEdge1Face[1] == pEdge2Face[0]) {
      return _WED_LESS;
   }
   return _WED_INCOMPARABLE;
}
*/
//
// End-of-file CGM_WED.CPP
//
